Insert Points

Starter Code Walkthrough

The previous concept showed how points are inserted into the tree. How about doing this in C++? Implementing a recursive helper function to insert points can be a very nice way to update Nodes. The basic idea is that the tree is traversed until the Node it arrives at is NULL, in which case a new Node is created and replaces the NULL Node. For assigning a Node, one way is to use a double pointer. You could pass in a pointer to the node, starting at root, and then when you want to replace a node you can dereference the double pointer and assign it to the newly created Node. Another way of achieving this is by using a pointer reference as well. For references, check out the code below for doing insertion in C++ but with a binary tree. The insertion for a KD-Tree will be very similar to this.

Example of Insertion for Binary Tree

Double Pointer

void insert(BinaryTreeNode **node, int data)
   {
      if(*node == NULL)
      {
        *node = getNewNode(data);
      }
      else if(data < (*node)->data)
      {
        insert(&(*node)->left, data);
      }
      else
      {
        insert(&(*node)->right, data);
      }
   }

Pointer Reference

void insert(BinaryTreeNode *&node, int data)
   {
      if(node == NULL)
      {
        node = getNewNode(data);
      }
      else if(data < node->data)
      {
        insert(node->left, data);
      }
      else
      {
        insert(node->right, data);
      }
   }

Instructions

Check out the quiz and try getting the resulting image from the previous concept, visually showing how each point is separating the x/y regions.

• In src/quiz/cluster/kdtree.h fill in the insert function.

Compile/Run

• In src/quiz/cluster , mkdir build
• cd build
• cmake ..
• make
• ./quizCluster

Solution